עצים (Trees):

• עץ הוא גרף לא מכוון, קשיר וחסר מעגלים (אציקלי).
• תנאים שקולים לעץ: בגרף לא מכוון $G=(V,E)$, התנאים הבאים הם שקולים:
  1. ש $G$ הוא עץ.
  2. ש $|E|=|V|-1$ ו-$G$ אינו מכיל מעגלים.
  3. ש $|E|=|V|-1$ ו-$G$ קשיר.
  4. שלכל זוג קודקודים בגרף ישנו מסלול פשוט יחיד ביניהם.
• הוספת והסרת צלעות:
  • אם נוסיף לעץ צלע חדשה $e\notin E$, הגרף החדש יכיל בדיוק מעגל פשוט אחד שעובר דרך הצלע $e$.
  • אם נסיר מאותו מעגל כל צלע אחרת $e^{\prime }$, הגרף יחזור להיות עץ מחדש.

בעיית העץ הפורש המינימלי (Minimum Spanning Tree - MST):

• קלט הבעיה: גרף קשיר ולא מכוון $G=(V,E)$ יחד עם פונקציית משקל לצלעות $w:E\to \mathbb{R}$.
• מטרת הבעיה: למצוא תת-גרף $T=(V,E_T)$ של $G$ המקיים:
  1. ש -$T$ הוא עץ.
  2. שסכום המשקלים של הצלעות ב-$T$, כלומר $\sum _{(u,v)\in E_T}w(u,v)$, הוא מינימלי.
• עץ המקיים את שני התנאים הללו מוגדר כעץ פורש מינימלי.
• 

האלגוריתם הגנרי למציאת MST:

• מתחזק קבוצת צלעות $A$ שהיא תת-קבוצה של עץ פורש מינימלי כלשהו. האלגוריתם מוסיף בכל שלב צלע שהיא בטוחה עבור $A$:

  • כלומר כזו שהוספתה ל-$A$ משאירה את $A$ כחלק מעץ פורש מינימלי.

• מושגי יסוד למציאת צלע בטוחה:

  • חתך:
    • חלוקה של קודקודי הגרף לשתי קבוצות זרות.
    • 
  • צלע חוצה חתך אם קצה אחד שלה נמצא בקבוצה אחת והשני בקבוצה השניה.
  • חתך מכבד קבוצת צלעות $A$ אם אף צלע מתוך $A$ לא חוצה את החתך.
  • צלע קלה:
    • מתוך כל הצלעות שחוצות את החתך, זוהי הצלע בעלת המשקל המינימלי.
    • 

• משפט מציאת צלע בטוחה: אם $A$ היא תת-קבוצה של MST כלשהו, קיים חתך שמכבד את $A$, והצלע $(u,v)$ היא צלע קלה שחוצה את החתך, אזי $(u,v)$ היא צלע בטוחה עבור $A$.

אלגוריתם קרוסקל (Kruskal's Algorithm):

• אלגוריתם הבונה את העץ באמצעות בחירת צלעות מהקלה אל הכבדה, תוך הימנעות מיצירת מעגלים. התהליך מתבצע על ידי מיזוג רכיבי קשירות עד לקבלת עץ יחיד.
• אופן הפעולה:
  • מאתחלים את $A$ כקבוצה ריקה, ויוצרים קבוצה נפרדת לכל קודקוד בגרף.
  • ממיינים את כל קבוצת הצלעות $E$ בסדר לא-יורד של משקלים.
  • עוברים על הצלעות הממוינות. עבור כל צלע $(u,v)$, בודקים האם הקודקודים שייכים לקבוצות שונות בעזרת (כדי למנוע מעגל).
  • אם הם מקבוצות (עצים) שונות, הצלע בטוחה. נוסיף אותה ל-$A$ ונאחד את הקבוצות.
  • 
  • 
• סיבוכיות זמן:
  • מיון הצלעות לוקח $O(E\log E)=O(E\log V)$.
  • תחזוקת מבנה הנתונים Disjoint Sets (יצירת קבוצות, חיפוש ואיחוד) לוקחת $O(E\alpha (V))$.
  • סך הכל סיבוכיות זמן הריצה היא $O(E\log V)$. במקרה שהצלעות מגיעות ממוינות מראש, הסיבוכיות תהיה $O(E\alpha (V))$.

אלגוריתם פרים (Prim's Algorithm):

• אלגוריתם זה עובד בצורה שונה - במקום לגדל יער של עצים שמתחברים, הוא מגדל עץ אחד יחיד שמתחיל מקודקוד שרירותי $r$ ומתפשט החוצה על ידי הוספת צלעות קלות.
• מבנה הנתונים:
  • האלגוריתם מנהל תור עדיפויות המכיל את כל הקודקודים שטרם צורפו לעץ. העדיפות בתור נקבעת לפי משקל הצלע הקלה ביותר שמחברת את הקודקוד אל העץ הנבנה.
  • עבור כל קודקוד שומרים גם שדה אבא ($\pi$) כדי לשחזר את העץ בסוף.
• אופן הפעולה:
  • מאתחלים את תור העדיפויות כך שקודקוד המקור $r$ יקבל מפתח 0 (שיישלף ראשון) ושאר הקודקודים מקבלים מפתח אינסוף ($\mathrm{\infty }$).
  • בכל איטרציה, מוציאים מתור העדיפויות את הקודקוד $u$ עם הערך המינימלי.
  • עוברים על כל השכנים $v$ של $u$. אם $v$ עדיין בתוך התור, והמשקל $w(u,v)$ קטן מהערך הנוכחי שלו ($v.key$), אז מעדכנים את ערכו להיות משקל הצלע בתור ומעדכנים את שדה האבא שלו ($v.\pi =u$).
  • 
  • 
• סיבוכיות זמן:
  • בניית תור העדיפויות והאתחול לוקחים $O(V)$.
  • שליפת המינימום מהתור מתבצעת $V$ פעמים בעלות כוללת של $O(V\log V)$
  • עדכון ערכי הקודקודים מתבצע לכל היותר כפעמיים לכל צלע, בעלות כוללת של $O(E\log V)$.
  • סך הכל סיבוכיות זמן הריצה היא $O(E\log V)$.